package algorithmic_data_structure.二叉树递归套路;


public class Code02_最大BST头节点 {
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
    class Ret{
        int min;
        int max;
        TreeNode maxBSTHead;
        int maxBSTSize;

        public Ret(int min, int max, TreeNode maxBSTHead, int maxBSTSize) {
            this.min = min;
            this.max = max;
            this.maxBSTHead = maxBSTHead;
            this.maxBSTSize = maxBSTSize;
        }
    }
    public TreeNode maxBSTHead(TreeNode root){
        return process(root).maxBSTHead;
    }

    private Ret process(TreeNode root) {
        if (root == null){
            return null;
        }
        Ret leftRet = process(root.left);
        Ret rightRet = process(root.right);
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        TreeNode maxBSTHead = root;//默认是自己，如果左右都是空那就是自己了
        int maxBSTSize = 1;
        if (leftRet != null){
            max = leftRet.max;
            maxBSTHead = leftRet.maxBSTHead;
            maxBSTSize = leftRet.maxBSTSize;
        }
        if (rightRet != null){
            min = rightRet.min;
            if (rightRet.maxBSTSize > maxBSTSize){
                maxBSTHead = leftRet.maxBSTHead;
                maxBSTSize = leftRet.maxBSTSize;
            }
        }
        //判断左右 是否为 BST ，如果都是最大的头肯定是自己啊
        if (
                (leftRet == null ? true : (leftRet.maxBSTHead == root.left && leftRet.max <= root.val))
                &&
                (rightRet == null ? true : (rightRet.maxBSTHead == root.right && rightRet.min >= root.val))
           ){
            maxBSTHead = root;
            maxBSTSize =
                    (leftRet == null ? 0 : leftRet.maxBSTSize) + (rightRet == null ? 0 : rightRet.maxBSTSize) + 1;
        }
        return new Ret(min,max,maxBSTHead,maxBSTSize);
    }
}
